#include<vector>

using namespace std;
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        int m = dp[0] = nums[0];

        for (int i = 1; i < n; i++) {

            if (dp[i - 1] >= 0) {
                dp[i] = nums[i] + dp[i - 1];
            }
            else {
                dp[i] = nums[i];
            }
            if (m < dp[i])
                m = dp[i];
        }

        return m;
    }
};